/**
 * 88. Merge Sorted Array
 * https://leetcode.com/problems/merge-sorted-array/
 */
package lc88;

public class Main {
  public static void main(String[] args) {
    int[] nums1 = {2,5,6,0,0,0};
    int[] nums2 = {1,2,3};
    int m = 3, n = 3;
    new Solution().merge(nums1, m, nums2, n);
    for (int i = 0; i < nums1.length; i++) {
      System.out.print(nums1[i] + " ");
    }
  }
}

class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    int[] r = new int[m + n];
    int n1 = 0, n2 = 0;
    for (int i = 0; i < r.length; i++) {
      if (n1 == m) {
        r[i] = nums2[n2++];
        continue;
      }
      if (n2 == n) {
        r[i] = nums1[n1++];
        continue;
      }
      if (nums1[n1] < nums2[n2]) {
        r[i] = nums1[n1++];
      } else {
        r[i] = nums2[n2++];
      }
    }

    for (int i = 0; i < r.length; i++) {
      nums1[i] = r[i];
    }
  }
}

/**
 * https://leetcode.com/problems/merge-sorted-array/discuss/222430/Java-Solution
 */
class Solution2
{
    public void merge(int[] A, int m, int[] B, int n) 
    {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        
        while(i >= 0 && j >= 0)
        {
            if(A[i] > B[j])
                A[k--] = A[i--];
            else
                A[k--] = B[j--];
                
        }
        
        while(j >= 0)
            A[k--] = B[j--];
    }
}
